Computer systems output data in either monochrome or color formats. In certain applications, the display of data in color has many advantages over the monochrome display of data. The use of color allows for easy identification of certain data on a display. For example, a red field could mean data entered incorrectly, whereas a green field could mean data entered correctly. The use of colors also allows sophisticated multicolor graphs, charts, and diagrams to be displayed and printed. Finally, the use of color in an application has a particular aesthetic appeal to computer users that is similar to the appeal color television has over black-and-white television.
Computer systems typically support a variety of color output devices, including video displays and printers. Each of these output devices has differing characteristics. For example, the IBM 8514/A graphics adapter, which provides, an interface between the computer and the display, provides the capability to display over 256,000 colors, but only 256, different colors can be displayed at one time. The IBM Enhanced Graphics Adapter (EGA) can display 64 colors, but only 16 different colors can be displayed at a time. When using these adapters, the program sending data to the adapter must specify which colors are the "active" colors; that is, the colors that currently are selected for display. Some other display devices, such as inkjet color printers, are capable of displaying only 16 colors, all of which are active.
Each application program that displays color data must account for the differences in the number of active colors the various graphics adapters support. Systems software, such as Microsoft's Windows, provides a device-independent application programming interface. A developer of application programs can use standard systems routines to display information on a color output device. The systems software adjusts the data to accommodate the differing characteristics of the graphics adapter, so the application programmer need not be concerned about the differing characteristics of the graphics adapters.
The visible spectrum of color can be characterized as a three-dimensional color space. Each color of the visible spectrum can be characterized as a three-dimensional color vector in a color coordinate system, such as the RGB red-green-blue) system typically used in the United States or the CIE (Commission Internationale de l'Eclairage) system typically used in Europe. Each color vector includes a color intensity value for each of the three color coordinates in the color coordinate system. In the RGB system, each color vector includes a color intensity value for each of the red, green, and blue color coordinates, while in the CIE system, the color components are referred to simply as X, Y, and Z.
Color output devices display the active colors using combinations of base colors. The base colors may or may not be the same as the color coordinates of the color coordinate system being used. The color coordinates refer to the colors used in the color coordinate system to internally represent an image; the base colors refer to the colors used to display the image using an output device. Color monitors typically employ red, green, and blue phosphor colors as the base colors and color printers typically use cyan, yellow, and magenta inks as the base colors. Each picture element (pel) on a display can be set to any one of the active colors by setting appropriate color intensity values for the base colors being used. For example, a low-intensity red value would appear as dim red and a high-intensity red value would appear as bright red. The IBM 8514/A can display 64 different color intensity values of each base color, but the IBM EGA can display only two different color intensity values for each base color.
The IBM 8514/A has 256 active colors selected from the 256,000 colors that it can display. Each active color can be represented in binary form using 8 bits. Each pel has associated with it an 8-bit value representing the active color to be displayed at that pel. By standard programming convention, the 8 bits are divided into 3 bits for red, 3 bits for green, and 2 bits for blue. Thus, eight different intensities of red and green are active, but only four intensities of blue are active. The IBM EGA has only 16 active colors. Thus, each pel has an associated 4-bit value. By standard programming convention, there is one red bit, one green bit, one blue bit, and one intensity bit (IBGR). The intensity bit selects either high or low intensity for all the colors. Thus, the three colors of a given pel can be displayed either in all high intensity or in all low intensity.
The device-independent application program interfaces provided by systems software can support a much larger number of active colors than is typically supported by graphics adapters that are used on personal computers. For example, the Microsoft Windows pro tram supports over 16 million active colors. An application program using Windows can specify 8 bits of red, 8 bits of green, and 8 bits of blue. Each 8-bit value represents an intensity level of the color between 0 and 255. To display bright red at a pel, the application would select an RGB value of high-intensity red and zero intensity green and blue, which is represented as (255,0,0). To display half intensity magenta (purple), the application may select an RGB value of (128,0,128), that is, half-intensity red and blue and zero intensity green.
The systems software maps the 8-bit values specified by the application program to the active colors of the output device. This is referred to as gamut mapping because the gamut of colors specified by the application program is mapped to the gamut of active colors of the output device. In computer systems using the IBM 8514/A, the systems software maps the three 8-bit values to one 8-bit value and for systems using the IBM EGA, it maps to one 4-bit value.
This mapping results in undesirable effects. An application may specify similar shades of a color using the three 8-bit values. However, the systems software may map the similar, but not identical, shades to the same active color. For example, the systems software maps the 256 possible intensity levels for green and blue to just 8 intensity levels for the IBM 8514/A. Thus, typically 32 different application-specified intensities are actually displayed at the same intensity.
Prior art systems attempt to overcome the color inaccuracy of individual pixels using two methods borrowed from black and white graphics: halftoning and error diffusion. Both halftoning and error diffusion (also known as types of dithering) are based on the physiological phenomenon of the human eye known as spatial averaging or spatial integration. Spatial averaging results from the inability of the human eye to differentiate individual pixels because they are too small. As a result of spatial averaging, humans perceive the average effect of a group of pixels. For example, a group of alternating black and white pixels would appear to be gray.
In prior art black and white systems employing error diffusion, the luminance value of each pixel in succession of an input image is compared with the luminance values that can be produced by the display device. The displayable luminance value that is closest to the input luminance value is displayed and the difference (i.e. the error) between the input luminance value and the displayed luminance value is diffused to adjacent pixels. Typically, the prior art systems employ a method known as the Floyd-Steinberg algorithm, which diffuses the error to pixels adjacent the current pixel by adding 7/16 of the error to the pixel to the right of the current pixel, 3/16 to the pixel below and to the left, 5/16 to the pixel immediately below and 1/16 to the pixel below and to the right.
In prior art color systems, error diffusion is applied to create a desired average color of a group of pixels. In these prior art color systems, an input image, represented by a two-dimensional array of color vector triplets (such as RGB vector triplets), is divided into three two-dimensional arrays of scalars (color planes) and each color plane is treated separately. In other words, the prior art systems employ error diffusion on three separate color planes or images, with each color plane consisting of one component (base color) of the color triplet. The three resultant images are then superimposed when they are output.
This prior art error diffusion process assumes the axis of the output device's color space is lined up with the axis of the image's color space (e.g., specifying pure red causes the device to output the purest red of which it is capable). Also, it assumes the interaction between the colorants in the three planes is accurately described by a linear relationship (i.e., ColorOf(M+N)=ColorOf(M)+ColorOf(N)). Furthermore, it assumes a linear relationship as the amount of a particular color is varied. ColorOf(c*M)=c*ColorOf(M). It is evident from looking at the inaccurate results of conventional color error diffusion as implemented in color printers, that these assumptions are not valid.